#include <bits/stdc++.h>

using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution1 {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p=head,*q=head,*r=head;
        if(nullptr==head||head->next==nullptr) return head;
        q=head->next;
        r=q->next;
        p->next=nullptr;
        q->next=p;

        while(r){
            p=q;
            q=r;
            r=r->next;
            q->next=p;
        }
        return q;
    }
};
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        stack<ListNode*> s;
        while(head){
            s.push(head);
            head=head->next;
        }
        head=s.top();s.pop();
        ListNode *p=head,*r=nullptr;
        while(!s.empty()){
            r=s.top();s.pop();
            p->next=r;
            p=r;
        }
        r->next=nullptr;
        return head;
    }
};

ListNode * h(vector<int> &num){
    int len=num.size();
    ListNode *p=new ListNode(num[0]);
    ListNode *head=p,*r=nullptr;
    for(int i=1;i<len;i++){
        r=new ListNode(num[i]);
        p->next=r;
        p=r;
    }
    return head;
}

int main(){
    vector<int> num={1,2,3};
    ListNode *p=h(num);
    ListNode *q=p;
    while(q){
        cout << q->val << " ";
        q=q->next;
    }cout << endl;
    Solution s;

    p=s.reverseList(p);
    while(p){
        cout << p->val<< " ";
        p=p->next;
    }cout << endl;



    return 0;
}